package com.classicInterview;

/**
 * 绘色，求RGGRR变成左侧都是R,右侧都是G的最小绘色次数
 *
 * @Author: huangzhigao
 * @Date: 2022/2/12 10:54
 */
public class Code3_Color {
    public int getMinColor(String s) {
        char[] chars = s.toCharArray();
        int N = chars.length;
        //统计i位置数组右侧R的个数
        int[] R = new int[N];
        R[N - 1] = chars[N - 1] == 'R' ? 1 : 0;
        for (int i = N - 2; i >= 0; i--) {
            R[i] = R[i + 1] + chars[i] == 'R' ? 1 : 0;
        }
        //统计i位置数组左侧G的个数
        int left = 0;
        int res = R[0];
        //以i为分割线，左右两侧绘色的最小次数
        for (int i = 0; i < N - 1; i++) {
            left += chars[i] == 'G' ? 1 : 0;
            res = Math.min(res, left + R[i + 1]);
        }


        return Math.min(res, left + (chars[N - 1] == 'G' ? 1 : 0));
    }
}
